package com.cqs.leetcode.graph;

import java.util.*;

/**
 * lixw
 * 2023/10/29
 */
public class Solution785 {


    public boolean isBipartite(int[][] graph) {


        //return new SolutionBFS().isBipartite(graph);
        return new SolutionDFS().isBipartite(graph);
    }

    class SolutionDFS {
        int[][] graph = null;
        int[] group = null;
        boolean[] visited = null;

        public boolean isBipartite(int[][] graph) {
            this.graph = graph;
            group = new int[graph.length];
            visited = new boolean[graph.length];
            int grpIdx = 1;
            for (int i = 0; i < graph.length; i++) {
                if (group[i] > 0) continue;
                if (!dfs(grpIdx, i)) return false;
            }
            return true;
        }

        private boolean dfs(int grpIdx, int vertex) {
            if (visited[vertex]) return true;
            visited[vertex] = true;
            //递归出口
            group[vertex] = grpIdx;
            for (int neighbor : graph[vertex]) {
                //neighbor已经存在分组， 若相邻顶点在一个分组， 不是二分图
                if (group[neighbor] == grpIdx || !dfs(3 - grpIdx, neighbor)) return false;
            }
            return  true;
        }
    }


    class SolutionBFS {

        /**
         * 0. 有效分组编号1-2, 0表示未分组。用一个数组保存各顶点的分组情况。
         * 1. 从0号顶点进行广度遍历，将当前点的相邻顶点存入队列
         * 2. 当遍历第i层的时候，找到对应的分组，遍历i+1的是否就是3-分组编号。
         * 3. 若相邻的顶点的分组和当前顶点的在同一层， 不是二分图
         * 4. 注意去重&不是连通图(多子图)
         *
         * @param graph
         * @return
         */
        public boolean isBipartite(int[][] graph) {
            // 0: 未分配 1: 分组1, 2: 分组2
            int[] group = new int[graph.length];
            Queue<Integer> q = new ArrayDeque<>();
            int groupIdx = 2; // 分组索引: 1, 2
            //是否进入过队列， 比q.contains()方法判断优化3ms->1ms
            boolean[] queued = new boolean[group.length];
            for (int i = 0; i < graph.length; i++) {
                //未分组
                if (group[i] > 0) continue;
                q.add(i);
                while (q.size() > 0) {
                    int size = q.size();
                    //反转分组; 1 ->2,   2 ->1
                    groupIdx = 3 - groupIdx;
                    for (int j = 0; j < size; j++) {
                        //当前"层级"分组
                        int vertex = q.poll();
                        group[vertex] = groupIdx;
                        //下一层级分组
                        for (int neighbor : graph[vertex]) {
                            //相邻的点 不能再一个分组
                            if (group[neighbor] == groupIdx) return false;
                            //处理过的点，不在处理， 避免死循环
                            //避免重复添加 (0,1) (0,2) (1,4) (2,4)
                            if (group[neighbor] > 0 || queued[neighbor]) continue;
                            q.add(neighbor);
                            queued[neighbor] = true;
                        }
                    }
                }
            }
            return true;
        }

        /**
         * BFS遍历
         * 声明２个集合，一个队列Q
         * 开始ｉ＝０号顶点
         * １．处理第ｉ号顶点，　将相邻的点放到X号集合, 并进入队列Q
         * ２．遍历队列Q，i分别等于队列中的元素，然后相邻的点进入队列，且放入相反的集合中
         * 3. 不存在一个元素出现在两个集合中，这是二分图
         * <p>
         * //若选在多个子图 怎么处理
         *
         * @param graph
         * @return
         */
        public boolean isBipartite1(int[][] graph) {
            boolean[][] groups = new boolean[2][graph.length];
            for (int i = 0; i < 2; i++) {
                groups[i] = new boolean[graph.length];
            }
            //是否进入过队列
            Queue<Integer> q = new ArrayDeque<>();
            q.add(0);
            int idx = 1;
            //点是否处理过
            while (q.size() > 0) {
                //变更集合编号
                idx = 1 - idx;
                final int size = q.size();
                for (int i = 0; i < size; i++) {
                    int vertex = q.poll(); //neighboring
                    groups[idx][vertex] = true;
                    int[] adjacent = graph[vertex];
                    for (int adj : adjacent) {
                        //若相邻节点和当前顶点出现在一个集合中， 不是二分图
                        if (groups[idx][adj]) {
                            return false;
                        }
                        //处理过的点 不需要在次进入队列中，避免重复处理
                        if (!groups[1 - idx][adj] && !q.contains(adj)) {
                            q.add(adj);
                        }
                    }
                }
                //若存在多个图
                if (q.size() == 0) {
                    for (int i = 0; i < graph.length; i++) {
                        if (!groups[1 - idx][i] && !groups[idx][i]) {
                            q.add(i);
                            break;
                        }
                    }
                }
            }
            return true;
        }
    }


}
